

<p><span style="font-size: small;">Durant ce TP, nous allons implanter diff&eacute;rents tests de primalit&eacute; et tenter de les comparer. Pour comparer deux tests, le temps utilis&eacute; est important, mais aussi la m&eacute;moire (est-ce que j'utilise des tableaux immenses, des entiers trop grands ?). En g&eacute;n&eacute;ral, les meilleurs algorithmes sont des compromis entre m&eacute;moire et temps. Pour chaque question, vous pouvez faire quelques tests rapides &agrave; chaque fois : jusqu'&agrave; quelle taille d'entiers est-ce qu'on g&egrave;re en moins d'une minute et sans avoir des bugs de d&eacute;passement de m&eacute;moire ? (Faites-le sur plus d'un exemple : en g&eacute;n&eacute;ral, si on essaie sur un entier pair ou multiple de 3, &ccedil;a va tr&egrave;s vite, mais on explose sur un nombre premier)<br /></span></p>
<p><span style="font-size: small;">Exercice 1 : &Eacute;chauffement.</span></p>
<p><span style="font-size: small;">Parce qu'il faut bien commencer par le d&eacute;but : &Eacute;crivez une fonction ForceBrute(n) qui teste si n est divisible par au moins un entier k&lt;n (quand peut-on s'arr&ecirc;ter ?).</span></p>

{{{id=3|
def bruteForce(n):
    if n<4: return True 
    if n%2==0: return False
    i=3
    sqr=n**(0.5)
    while i<sqr:
        if n%i==0: return False
        i+=2
    return True
///
}}}

<p><span style="font-size: small;">Exercice 2 : Th&eacute;or&egrave;me de Wilson.</span></p>
<p><span style="font-size: small;">On a vu en cours que n est premier si et seulement si (n-1)! = 1 [n]. Construisez un test Wilson(n) qui utilise ce r&eacute;sultat pour tester si n est premier.</span></p>

{{{id=7|
def wilson(n):
    i,temp=1,1
    while i<n-1:
        temp*=i
        temp%=n
        if not temp: return False
        i+=1
    return temp%n==n-1
///
}}}

<p><span style="font-size: small;">Exercice 3 : Petit th&eacute;or&egrave;me de Fermat.</span></p>
<!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } -->
<p><span style="font-size: small;">On sait que si p est premier, alors pour tout a, a<sup>p-1</sup>=1 [p]. L'inverse n'est pas toujours vrai, mais on peut esp&eacute;rer rep&eacute;rer des nombres non premiers comme &ccedil;a. &Eacute;crivez une fonction Fermat(n) qui :</span></p>
<p><span style="font-size: small;">- prend un entier a au hasard entre 2 et n-1 ;</span></p>
<p style="margin-bottom: 0cm;"><span style="font-size: small;">- teste si a<sup>n-1</sup>=1 [n] ;</span></p>
<p style="margin-bottom: 0cm"><span style="font-size: small;">- renvoie True si n est potentiellement premier, False sinon.</span></p>
<p style="margin-bottom: 0cm"><span style="font-size: small;">Pour la premi&egrave;re partie, on pourra utiliser randint(a,b) qui renvoie un entier entre a et b.&nbsp; <br /></span></p>

{{{id=8|
def Fermat(n,times=12):
    if n<4: return True
    for i in range(times):
        if not (randrange(2,n-1)*1).powermod(n-1,n)==1: return False
    return True

#timeit("Fermat(2**424242-1)")
#for i in range(445): 
#    if Fermat(4000): print "Error"
///
}}}

<p><span style="font-size: small;">Exercice 4 : Exponentiation rapide.</span></p>
<!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } -->
<p><span style="font-size: small;">On veut acc&eacute;l&eacute;rer l'algorithme pr&eacute;c&eacute;dent (j'esp&egrave;re que vous n'avez pas fait a**(n-1) ?) en &eacute;tant plus efficace sur le calcul de la puissance. &Eacute;crire une fonction ExpoRapide(a,k,n) qui calcule </span><span style="font-size: small;">a<sup>k </sup>[n] en distinguant les cas :</span></p>
<!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } --><!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } --><!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } --><!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } -->
<p><span style="font-size: small;">- Si k est pair, on fait a<sup>k</sup> = a<sup>k/2</sup>&nbsp; * a<sup>k/2</sup>;</span></p>
<!-- 		@page { margin: 2cm } 		P { margin-bottom: 0.21cm } -->
<p><span style="font-size: small;">- Si k est impair, on fait a<sup>k </sup>= a * a<sup>(k-1)/2</sup> * a<sup>(k-1)/2</sup></span></p>
<p><span style="font-size: small;">On peut par exemple utiliser la r&eacute;cursion en appelant la fonction qu'on est en train d'&eacute;crire (sans oublier de faire attention &agrave; ce qui se passe pour k=1).</span></p>

{{{id=11|
def expolution(a,k,n):
    if k==1: return a
    if k%2==0:
        temp=expolution(a,k/2,n)%n
        temp*=2
    else:
        temp=expolution(a,(k-1)/2,n)%n
        temp=a*temp*temp
    return temp

for a in range(44,89):
    a=1*(a)
    #timeit("a.powermod(55,12)")
    #timeit("expolution(a,55,12)")
///
}}}

<p><span style="font-size: small;">Exercice 5 : D&eacute;marche scientifique.</span></p>
<p><span style="font-size: small;">On aimerait avoir une id&eacute;e du taux d'erreur de l'algorithme pr&eacute;c&eacute;dent (nombres non premiers pour lesquels la r&eacute;ponse est True), par exemple pour les entiers &agrave; 5 chiffres. On peut tester sur tous les nombres de 1000 &agrave; 9999...(non conseill&eacute;), ou bien en prendre quelques centaines au hasard. &Eacute;crivez une fonction TestFermat() qui it&egrave;re cette op&eacute;ration jusqu'&agrave; ce qu'on ait atteint 10 erreurs (environ 2 minutes). Quel est la probabilit&eacute; de r&eacute;ussite du test ?<br /></span></p>

{{{id=9|
def TestFermat(n,times=1):
    if bruteForce(n)!=Fermat(n,times):
        return True
    return False

def percentage(times=10):
    res,i=[],0
    while len(res)<11:
        if TestFermat(randrange(1000,10000)*1,times=times): res+=[i]
        i+=1
    return i

res=[]
for i in range(2,20): res.append([i,percentage(times=i)])

a=Graphics()+point(res)
#print res
a.show()
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<p><span style="font-size: small;">Exercice 6 : <br /></span></p>
<p><span style="font-size: small;">Plut&ocirc;t que de prendre la valeur de a au hasard, on peut prendre a=2. Quel serait l'inter&ecirc;t en termes de vitesse ? &Eacute;crivez le programme Fermat2(n), puis testez sa probabilit&eacute; d'erreur sur toutes les valeurs de 1 &agrave; 10000. <br /></span></p>

{{{id=14|
def Fermat2(n,a=7):
    if n<4: return True
    return a.powermod(n-1,n)==1

def TestFermat2(n):
    if bruteForce(n)!=Fermat2(n): return True
    return False

def percentage2(n):
    res,i=[],0
    while len(res)<11 and i<10000:
        if TestFermat2(n): res+=[i]
        i+=1
    return i/(len(res)+1)

res=[]

for i in range(1,1001):
    res.append([i,percentage2(i*1)])
    if i%100==0: print i

print res

re=[]
for a,b in res:
    if b<1000: re.append([a,b])
a=Graphics()+point(re)
print set([i for i,j in re]),len(set([i for i,j in re]))/1000
a.show()
///
100
200
300
400
500
600
700
800
900
1000
[[1, 10000], [2, 10000], [3, 10000], [4, 10000], [5, 10000], [6, 11/12], [7, 11/12], [8, 10000], [9, 11/12], [10, 10000], [11, 10000], [12, 10000], [13, 10000], [14, 10000], [15, 10000], [16, 10000], [17, 10000], [18, 10000], [19, 10000], [20, 10000], [21, 10000], [22, 10000], [23, 10000], [24, 10000], [25, 10000], [26, 10000], [27, 10000], [28, 10000], [29, 10000], [30, 10000], [31, 10000], [32, 10000], [33, 10000], [34, 10000], [35, 10000], [36, 10000], [37, 10000], [38, 10000], [39, 10000], [40, 10000], [41, 10000], [42, 10000], [43, 10000], [44, 10000], [45, 10000], [46, 10000], [47, 10000], [48, 10000], [49, 11/12], [50, 10000], [51, 10000], [52, 10000], [53, 10000], [54, 10000], [55, 10000], [56, 10000], [57, 10000], [58, 10000], [59, 10000], [60, 10000], [61, 10000], [62, 10000], [63, 10000], [64, 10000], [65, 10000], [66, 10000], [67, 10000], [68, 10000], [69, 10000], [70, 10000], [71, 10000], [72, 10000], [73, 10000], [74, 10000], [75, 10000], [76, 10000], [77, 10000], [78, 10000], [79, 10000], [80, 10000], [81, 10000], [82, 10000], [83, 10000], [84, 10000], [85, 10000], [86, 10000], [87, 10000], [88, 10000], [89, 10000], [90, 10000], [91, 10000], [92, 10000], [93, 10000], [94, 10000], [95, 10000], [96, 10000], [97, 10000], [98, 10000], [99, 10000], [100, 10000], [101, 10000], [102, 10000], [103, 10000], [104, 10000], [105, 10000], [106, 10000], [107, 10000], [108, 10000], [109, 10000], [110, 10000], [111, 10000], [112, 10000], [113, 10000], [114, 10000], [115, 10000], [116, 10000], [117, 10000], [118, 10000], [119, 10000], [120, 10000], [121, 11/12], [122, 10000], [123, 10000], [124, 10000], [125, 10000], [126, 10000], [127, 10000], [128, 10000], [129, 10000], [130, 10000], [131, 10000], [132, 10000], [133, 10000], [134, 10000], [135, 10000], [136, 10000], [137, 10000], [138, 10000], [139, 10000], [140, 10000], [141, 10000], [142, 10000], [143, 10000], [144, 10000], [145, 10000], [146, 10000], [147, 10000], [148, 10000], [149, 10000], [150, 10000], [151, 10000], [152, 10000], [153, 10000], [154, 10000], [155, 10000], [156, 10000], [157, 10000], [158, 10000], [159, 10000], [160, 10000], [161, 10000], [162, 10000], [163, 10000], [164, 10000], [165, 10000], [166, 10000], [167, 10000], [168, 10000], [169, 11/12], [170, 10000], [171, 10000], [172, 10000], [173, 10000], [174, 10000], [175, 10000], [176, 10000], [177, 10000], [178, 10000], [179, 10000], [180, 10000], [181, 10000], [182, 10000], [183, 10000], [184, 10000], [185, 10000], [186, 10000], [187, 10000], [188, 10000], [189, 10000], [190, 10000], [191, 10000], [192, 10000], [193, 10000], [194, 10000], [195, 10000], [196, 10000], [197, 10000], [198, 10000], [199, 10000], [200, 10000], [201, 10000], [202, 10000], [203, 10000], [204, 10000], [205, 10000], [206, 10000], [207, 10000], [208, 10000], [209, 10000], [210, 10000], [211, 10000], [212, 10000], [213, 10000], [214, 10000], [215, 10000], [216, 10000], [217, 10000], [218, 10000], [219, 10000], [220, 10000], [221, 10000], [222, 10000], [223, 10000], [224, 10000], [225, 10000], [226, 10000], [227, 10000], [228, 10000], [229, 10000], [230, 10000], [231, 10000], [232, 10000], [233, 10000], [234, 10000], [235, 10000], [236, 10000], [237, 10000], [238, 10000], [239, 10000], [240, 10000], [241, 10000], [242, 10000], [243, 10000], [244, 10000], [245, 10000], [246, 10000], [247, 10000], [248, 10000], [249, 10000], [250, 10000], [251, 10000], [252, 10000], [253, 10000], [254, 10000], [255, 10000], [256, 10000], [257, 10000], [258, 10000], [259, 10000], [260, 10000], [261, 10000], [262, 10000], [263, 10000], [264, 10000], [265, 10000], [266, 10000], [267, 10000], [268, 10000], [269, 10000], [270, 10000], [271, 10000], [272, 10000], [273, 10000], [274, 10000], [275, 10000], [276, 10000], [277, 10000], [278, 10000], [279, 10000], [280, 10000], [281, 10000], [282, 10000], [283, 10000], [284, 10000], [285, 10000], [286, 10000], [287, 10000], [288, 10000], [289, 11/12], [290, 10000], [291, 10000], [292, 10000], [293, 10000], [294, 10000], [295, 10000], [296, 10000], [297, 10000], [298, 10000], [299, 10000], [300, 10000], [301, 10000], [302, 10000], [303, 10000], [304, 10000], [305, 10000], [306, 10000], [307, 10000], [308, 10000], [309, 10000], [310, 10000], [311, 10000], [312, 10000], [313, 10000], [314, 10000], [315, 10000], [316, 10000], [317, 10000], [318, 10000], [319, 10000], [320, 10000], [321, 10000], [322, 10000], [323, 10000], [324, 10000], [325, 11/12], [326, 10000], [327, 10000], [328, 10000], [329, 10000], [330, 10000], [331, 10000], [332, 10000], [333, 10000], [334, 10000], [335, 10000], [336, 10000], [337, 10000], [338, 10000], [339, 10000], [340, 10000], [341, 10000], [342, 10000], [343, 10000], [344, 10000], [345, 10000], [346, 10000], [347, 10000], [348, 10000], [349, 10000], [350, 10000], [351, 10000], [352, 10000], [353, 10000], [354, 10000], [355, 10000], [356, 10000], [357, 10000], [358, 10000], [359, 10000], [360, 10000], [361, 11/12], [362, 10000], [363, 10000], [364, 10000], [365, 10000], [366, 10000], [367, 10000], [368, 10000], [369, 10000], [370, 10000], [371, 10000], [372, 10000], [373, 10000], [374, 10000], [375, 10000], [376, 10000], [377, 10000], [378, 10000], [379, 10000], [380, 10000], [381, 10000], [382, 10000], [383, 10000], [384, 10000], [385, 10000], [386, 10000], [387, 10000], [388, 10000], [389, 10000], [390, 10000], [391, 10000], [392, 10000], [393, 10000], [394, 10000], [395, 10000], [396, 10000], [397, 10000], [398, 10000], [399, 10000], [400, 10000], [401, 10000], [402, 10000], [403, 10000], [404, 10000], [405, 10000], [406, 10000], [407, 10000], [408, 10000], [409, 10000], [410, 10000], [411, 10000], [412, 10000], [413, 10000], [414, 10000], [415, 10000], [416, 10000], [417, 10000], [418, 10000], [419, 10000], [420, 10000], [421, 10000], [422, 10000], [423, 10000], [424, 10000], [425, 10000], [426, 10000], [427, 10000], [428, 10000], [429, 10000], [430, 10000], [431, 10000], [432, 10000], [433, 10000], [434, 10000], [435, 10000], [436, 10000], [437, 10000], [438, 10000], [439, 10000], [440, 10000], [441, 10000], [442, 10000], [443, 10000], [444, 10000], [445, 10000], [446, 10000], [447, 10000], [448, 10000], [449, 10000], [450, 10000], [451, 10000], [452, 10000], [453, 10000], [454, 10000], [455, 10000], [456, 10000], [457, 10000], [458, 10000], [459, 10000], [460, 10000], [461, 10000], [462, 10000], [463, 10000], [464, 10000], [465, 10000], [466, 10000], [467, 10000], [468, 10000], [469, 10000], [470, 10000], [471, 10000], [472, 10000], [473, 10000], [474, 10000], [475, 10000], [476, 10000], [477, 10000], [478, 10000], [479, 10000], [480, 10000], [481, 10000], [482, 10000], [483, 10000], [484, 10000], [485, 10000], [486, 10000], [487, 10000], [488, 10000], [489, 10000], [490, 10000], [491, 10000], [492, 10000], [493, 10000], [494, 10000], [495, 10000], [496, 10000], [497, 10000], [498, 10000], [499, 10000], [500, 10000], [501, 10000], [502, 10000], [503, 10000], [504, 10000], [505, 10000], [506, 10000], [507, 10000], [508, 10000], [509, 10000], [510, 10000], [511, 10000], [512, 10000], [513, 10000], [514, 10000], [515, 10000], [516, 10000], [517, 10000], [518, 10000], [519, 10000], [520, 10000], [521, 10000], [522, 10000], [523, 10000], [524, 10000], [525, 10000], [526, 10000], [527, 10000], [528, 10000], [529, 11/12], [530, 10000], [531, 10000], [532, 10000], [533, 10000], [534, 10000], [535, 10000], [536, 10000], [537, 10000], [538, 10000], [539, 10000], [540, 10000], [541, 10000], [542, 10000], [543, 10000], [544, 10000], [545, 10000], [546, 10000], [547, 10000], [548, 10000], [549, 10000], [550, 10000], [551, 10000], [552, 10000], [553, 10000], [554, 10000], [555, 10000], [556, 10000], [557, 10000], [558, 10000], [559, 10000], [560, 10000], [561, 11/12], [562, 10000], [563, 10000], [564, 10000], [565, 10000], [566, 10000], [567, 10000], [568, 10000], [569, 10000], [570, 10000], [571, 10000], [572, 10000], [573, 10000], [574, 10000], [575, 10000], [576, 10000], [577, 10000], [578, 10000], [579, 10000], [580, 10000], [581, 10000], [582, 10000], [583, 10000], [584, 10000], [585, 10000], [586, 10000], [587, 10000], [588, 10000], [589, 10000], [590, 10000], [591, 10000], [592, 10000], [593, 10000], [594, 10000], [595, 10000], [596, 10000], [597, 10000], [598, 10000], [599, 10000], [600, 10000], [601, 10000], [602, 10000], [603, 10000], [604, 10000], [605, 10000], [606, 10000], [607, 10000], [608, 10000], [609, 10000], [610, 10000], [611, 10000], [612, 10000], [613, 10000], [614, 10000], [615, 10000], [616, 10000], [617, 10000], [618, 10000], [619, 10000], [620, 10000], [621, 10000], [622, 10000], [623, 10000], [624, 10000], [625, 10000], [626, 10000], [627, 10000], [628, 10000], [629, 10000], [630, 10000], [631, 10000], [632, 10000], [633, 10000], [634, 10000], [635, 10000], [636, 10000], [637, 10000], [638, 10000], [639, 10000], [640, 10000], [641, 10000], [642, 10000], [643, 10000], [644, 10000], [645, 10000], [646, 10000], [647, 10000], [648, 10000], [649, 10000], [650, 10000], [651, 10000], [652, 10000], [653, 10000], [654, 10000], [655, 10000], [656, 10000], [657, 10000], [658, 10000], [659, 10000], [660, 10000], [661, 10000], [662, 10000], [663, 10000], [664, 10000], [665, 10000], [666, 10000], [667, 10000], [668, 10000], [669, 10000], [670, 10000], [671, 10000], [672, 10000], [673, 10000], [674, 10000], [675, 10000], [676, 10000], [677, 10000], [678, 10000], [679, 10000], [680, 10000], [681, 10000], [682, 10000], [683, 10000], [684, 10000], [685, 10000], [686, 10000], [687, 10000], [688, 10000], [689, 10000], [690, 10000], [691, 10000], [692, 10000], [693, 10000], [694, 10000], [695, 10000], [696, 10000], [697, 10000], [698, 10000], [699, 10000], [700, 10000], [701, 10000], [702, 10000], [703, 11/12], [704, 10000], [705, 10000], [706, 10000], [707, 10000], [708, 10000], [709, 10000], [710, 10000], [711, 10000], [712, 10000], [713, 10000], [714, 10000], [715, 10000], [716, 10000], [717, 10000], [718, 10000], [719, 10000], [720, 10000], [721, 10000], [722, 10000], [723, 10000], [724, 10000], [725, 10000], [726, 10000], [727, 10000], [728, 10000], [729, 10000], [730, 10000], [731, 10000], [732, 10000], [733, 10000], [734, 10000], [735, 10000], [736, 10000], [737, 10000], [738, 10000], [739, 10000], [740, 10000], [741, 10000], [742, 10000], [743, 10000], [744, 10000], [745, 10000], [746, 10000], [747, 10000], [748, 10000], [749, 10000], [750, 10000], [751, 10000], [752, 10000], [753, 10000], [754, 10000], [755, 10000], [756, 10000], [757, 10000], [758, 10000], [759, 10000], [760, 10000], [761, 10000], [762, 10000], [763, 10000], [764, 10000], [765, 10000], [766, 10000], [767, 10000], [768, 10000], [769, 10000], [770, 10000], [771, 10000], [772, 10000], [773, 10000], [774, 10000], [775, 10000], [776, 10000], [777, 10000], [778, 10000], [779, 10000], [780, 10000], [781, 10000], [782, 10000], [783, 10000], [784, 10000], [785, 10000], [786, 10000], [787, 10000], [788, 10000], [789, 10000], [790, 10000], [791, 10000], [792, 10000], [793, 10000], [794, 10000], [795, 10000], [796, 10000], [797, 10000], [798, 10000], [799, 10000], [800, 10000], [801, 10000], [802, 10000], [803, 10000], [804, 10000], [805, 10000], [806, 10000], [807, 10000], [808, 10000], [809, 10000], [810, 10000], [811, 10000], [812, 10000], [813, 10000], [814, 10000], [815, 10000], [816, 10000], [817, 11/12], [818, 10000], [819, 10000], [820, 10000], [821, 10000], [822, 10000], [823, 10000], [824, 10000], [825, 10000], [826, 10000], [827, 10000], [828, 10000], [829, 10000], [830, 10000], [831, 10000], [832, 10000], [833, 10000], [834, 10000], [835, 10000], [836, 10000], [837, 10000], [838, 10000], [839, 10000], [840, 10000], [841, 11/12], [842, 10000], [843, 10000], [844, 10000], [845, 10000], [846, 10000], [847, 10000], [848, 10000], [849, 10000], [850, 10000], [851, 10000], [852, 10000], [853, 10000], [854, 10000], [855, 10000], [856, 10000], [857, 10000], [858, 10000], [859, 10000], [860, 10000], [861, 10000], [862, 10000], [863, 10000], [864, 10000], [865, 10000], [866, 10000], [867, 10000], [868, 10000], [869, 10000], [870, 10000], [871, 10000], [872, 10000], [873, 10000], [874, 10000], [875, 10000], [876, 10000], [877, 10000], [878, 10000], [879, 10000], [880, 10000], [881, 10000], [882, 10000], [883, 10000], [884, 10000], [885, 10000], [886, 10000], [887, 10000], [888, 10000], [889, 10000], [890, 10000], [891, 10000], [892, 10000], [893, 10000], [894, 10000], [895, 10000], [896, 10000], [897, 10000], [898, 10000], [899, 10000], [900, 10000], [901, 10000], [902, 10000], [903, 10000], [904, 10000], [905, 10000], [906, 10000], [907, 10000], [908, 10000], [909, 10000], [910, 10000], [911, 10000], [912, 10000], [913, 10000], [914, 10000], [915, 10000], [916, 10000], [917, 10000], [918, 10000], [919, 10000], [920, 10000], [921, 10000], [922, 10000], [923, 10000], [924, 10000], [925, 10000], [926, 10000], [927, 10000], [928, 10000], [929, 10000], [930, 10000], [931, 10000], [932, 10000], [933, 10000], [934, 10000], [935, 10000], [936, 10000], [937, 10000], [938, 10000], [939, 10000], [940, 10000], [941, 10000], [942, 10000], [943, 10000], [944, 10000], [945, 10000], [946, 10000], [947, 10000], [948, 10000], [949, 10000], [950, 10000], [951, 10000], [952, 10000], [953, 10000], [954, 10000], [955, 10000], [956, 10000], [957, 10000], [958, 10000], [959, 10000], [960, 10000], [961, 11/12], [962, 10000], [963, 10000], [964, 10000], [965, 10000], [966, 10000], [967, 10000], [968, 10000], [969, 10000], [970, 10000], [971, 10000], [972, 10000], [973, 10000], [974, 10000], [975, 10000], [976, 10000], [977, 10000], [978, 10000], [979, 10000], [980, 10000], [981, 10000], [982, 10000], [983, 10000], [984, 10000], [985, 10000], [986, 10000], [987, 10000], [988, 10000], [989, 10000], [990, 10000], [991, 10000], [992, 10000], [993, 10000], [994, 10000], [995, 10000], [996, 10000], [997, 10000], [998, 10000], [999, 10000], [1000, 10000]]
set([289, 961, 325, 6, 7, 9, 841, 49, 529, 561, 169, 121, 703, 817, 361]) 3/200
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<p><span style="font-size: small;">Exercice 7 : Notez que sur une entr&eacute;e donn&eacute;e, la r&eacute;ponse du programme pr&eacute;c&eacute;dent n'est pas al&eacute;atoire. Comment faire pour en tirer un programme qui ne commette aucune erreur sur les entr&eacute;es &lt;10000 ?</span></p>

{{{id=23|
x= set([289, 961, 529, 9, 841, 49, 949, 169, 25, 91, 671, 703, 286, 361])
y= set([289, 961, 4, 5, 529, 9, 781, 841, 49, 561, 25, 121, 217, 124, 169, 361])
z= set([899, 133, 9, 529, 403, 25, 5, 289, 931, 169, 901, 703, 961, 841,589, 469, 217, 91, 871, 361, 493, 247, 121, 637, 341])
k= set([289, 961, 325, 6, 7, 9, 841, 49, 529, 561, 169, 121, 703, 817,361])

#(x.union(y).union(k)).difference
(x.intersection(y).intersection(k))
///
set([289, 961, 529, 9, 49, 841, 169, 361])
}}}

<p><span style="font-size: small;">Exercice 8 : factorisation de Pollard p-1<br /></span></p>
<p><span style="font-size: small;">On suppose n=pq, avec p,q premiers. On se donne B une borne assez grande et 1&lt;g&lt;n un nombre quelconque 'testeur'. On suppose que les facteurs de p-1 sont suffisamment petits pour que (p-1) divise B!. On&nbsp; consid&egrave;re alors a=g^(B!) mod n, qui doit &ecirc;tre congru &agrave; 1 modulo p, par le petit th&eacute;or&egrave;me de Fermat. Ainsi p divise (a-1) et n, donc le pgcd(a-1,n), s'il est diff&eacute;rent de 1 et n, est un diviseur non trivial de n. On a factoris&eacute; n.&nbsp;&nbsp; </span></p>
<p><span style="font-size: small;">&Eacute;crire une procedure PollardTest(n,B,g) qui effectue l'algorithme (p-1) de Pollard pour le nombre testeur g.&nbsp; Puis &eacute;crire une procedure Pollard(n,B) qui&nbsp; effectue les tests de Pollard&nbsp; 121 avec des testeurs g tels que 1&lt;g&lt;n et s'arr&ecirc;te si elle trouve un facteur de n ou si tous les g possibles ont &eacute;t&eacute; test&eacute;s.&nbsp; Appliquer cette proc&eacute;dure sur n = 139*197 et retrouver p,q. <br /></span></p>

{{{id=18|
for a in [289, 961, 529, 9, 49, 841, 169, 361]: print a.is_prime()
///
False
False
False
False
False
False
False
False
}}}

<p><span style="font-size: small;">Exercice 9 (*) : "Un groupe est un ensemble muni d'une loi"</span></p>
<p><span style="font-size: small;">Si vous &ecirc;tes arriv&eacute;s l&agrave;, vous avez davantage besoin de faire des maths que de l'info. On veut compter le nombre de groupes finis non isomporhes de taille n. Autrement dit, il s'agit du nombre de choix de lois de groupe diff&eacute;rentes sur [a1,...,an] telles que les groupes obtenus ne sont pas isomorphes. Regarder &agrave; la main les cas 3 et 4. Puis, faites la version facile en testant toutes les op&eacute;rations possibles puis en v&eacute;rifiant que c'est une loi, et ensuite en testant tous les isomorphismes possibles. Enfin, tentez d'am&eacute;liorer l'algorithme en &eacute;vitant les op&eacute;rations inutiles.</span></p>

{{{id=22|

///
}}}

{{{id=24|

///
}}}